package com.heima.algorithm.sort;

/**
 * <h3>计数排序</h3>
 * <ol>
 *     <li>找到最大值，创建一个最大值 + 1的count数组</li>
 *     <li>count数组的索引对应原始数组的元素，值用来统计该元素出现的次数</li>
 *     <li>遍历count数组生成遍历好的数组，索引是元素，值是出现次数，从低到高统计索引出现次数</li>
 * </ol>
 * <p>前提：待排序元素 >= 0且最大值不能太大</p>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/5 23:06
 */
public class CountingSortPositive {
    //（1）非比较排序算法
    //（2）时间复杂度：O(N + K)，空间复杂度：O(N + K)，N为数组长度，K为count数组长度，稳定：是

    /**
     * 计数排序
     * @param arr 待排序数组
     */
    public static void countingSort(int[] arr){
        int max = arr[0]; // 假设第一个元素为最大值
        // 找到最大值
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }
        // 创建count数组
        int[] count = new int[max + 1];
        // 统计每个元素出现的次数
        for (int j : arr) {
            count[j]++;
        }
        // 遍历count数组，生成排序好的数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            for (int j = 0; j < count[i]; j++) {
                arr[index++] = i;
            }
        }
    }
}
